package leetcode.code004;

public class Solution extends Solution004 {

	@Override
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;
		int len = len1 + len2;
		boolean odd = ((len & 1) == 1);// 奇数
		int k = odd ? ((len >> 1) + 1) : (len >> 1);// 第几个数
		int m = 0;
		int p1 = 0;//
		int p2 = 0;
		int drop1 = 0;//nums1舍掉的数据
		int drop2 = 0;//nums2舍掉的数据
		int left = 0;
		while (true) {
			left = k - drop1 - drop2;
			if (drop1 == len1) {
				return odd ? nums2[drop2 + left - 1] : (nums2[drop2 + left - 1] + nums2[drop2 + left]) / 2.0;
			}
			if (drop2 == len2) {
				return odd ? nums1[drop1 + left - 1] : (nums1[drop1 + left - 1] + nums1[drop1 + left]) / 2.0;
			}
			if (left == 1) {
				if (odd) {
					return nums1[drop1] < nums2[drop2] ? nums1[drop1] : nums2[drop2];
				} else {
					if (nums1[drop1] < nums2[drop2]) {
						if (drop1 + 1 < len1)
							return (Math.min(nums2[drop2], nums1[drop1 + 1]) + nums1[drop1]) / 2.0;
						else
							return (nums2[drop2] + nums1[drop1]) / 2.0;
					} else {
						if (drop2 + 1 < len2)
							return (Math.min(nums1[drop1], nums2[drop2 + 1]) + nums2[drop2]) / 2.0;
						else
							return (nums1[drop1] + nums2[drop2]) / 2.0;
					}
				}
			}
			m = (left >> 1) - 1;
			p1 = m < len1 ? drop1 + m : len1 - 1;
			p2 = m < len2 ? drop2 + m : len2 - 1;
			if (nums1[p1] <= nums2[p2]) {// 指针移动，数组舍去
				drop1 = p1 + 1;
			} else {
				drop2 = p2 + 1;
			}
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();

//		System.out.println(1 / 2);
	}

}
